package main

import "fmt"

func main()  {
	arr := []int{7,6,2,8,9,1}
	insertSort(arr)
	fmt.Println(arr)
}

/**
  插值排序 时间复杂度 O(n2)
	第一次循环 7,6,2,8,9,1
		从第二个数开始 6
		1.比较前一个数 7 ，如果小于前一个数，则前一个数 7 往后移一位
		如：6 < 7,则7替换原来的位置 7 7 2 8 9 1
		2.如果前面没有数据了，则把原来的第二位的数6放在第一个位置 6 7 2 8 9 1
    第二次循环 6 7 2 8 9 1
		从第三个数开始 2 < 7 第二个数后移一位 6 7 7 8 9 1
		2 < 6 第一个数后移一位 6 6 7 8 9 1
		前面没数了 原来的第三个数替换第一个数 2 6 7 8 9 1
	......
 */
func insertSort(arr []int) {

	//i从1开始
	for j := 1; j < len(arr); j++ {

		//第i个数
		value := arr[j]
		//前一个数的索引
		i := j-1

		//7 > 2 第一次比较
		//6 > 2 第二次比较
		for  i >= 0 &&  arr[i]>value {

			//6,7,7,8,9,1
			//6,6,7,8,9,1
			arr[i+1] = arr[i]
			i=i-1

		}
		//2,6,7,8,9,1
		arr[i+1] = value

	}
}